#include <iostream>
using namespace std;
typedef long long ll;

// 扩展欧几里得算法，返回gcd，并计算出x,y满足ax+by=gcd(a,b)
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; // 当 b==0, ax=gcd(a,0)=a, x=1,y=0
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x); // 注意这里交换x,y的位置
    y -= (a / b) * x;
    return d;
}

/**
 * https://www.luogu.com.cn/problem/P1082
 */
int main() {
    ll a, b;
    cin >> a >> b;
    ll x, y;
    exgcd(a, b, x, y);
    x = (x % b + b) % b; // 转换为最小正整数解
    cout << x << endl;
    return 0;
}
